package com.topcoder.srm211;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Stack;

/**
 * In one mode of the grafix software package, the user blocks off portions 
 * of a masking layer using opaque rectangles. The bitmap used as the masking 
 * layer is 400 pixels tall and 600 pixels wide. Once the rectangles have been 
 * blocked off, the user can perform painting actions through the remaining 
 * areas of the masking layer, known as holes. To be precise, each hole is a 
 * maximal collection of contiguous pixels that are not covered by any of the 
 * opaque rectangles. Two pixels are contiguous if they share an edge, and 
 * contiguity is transitive.
 * 
 * You are given a String[] named rectangles, the elements of which specify the 
 * rectangles that have been blocked off in the masking layer. Each String in 
 * rectangles consists of four integers separated by single spaces, with no 
 * additional spaces in the string. The first two integers are the window 
 * coordinates of the top left pixel in the given rectangle, and the last two 
 * integers are the window coordinates of its bottom right pixel. The window 
 * coordinates of a pixel are a pair of integers specifying the row number 
 * and column number of the pixel, in that order. Rows are numbered from top 
 * to bottom, starting with 0 and ending with 399. Columns are numbered from 
 * left to right, starting with 0 and ending with 599. Every pixel within and 
 * along the border of the rectangle defined by these opposing corners is 
 * blocked off.
 * 
 * Return a int[] containing the area, in pixels, of every hole in the 
 * resulting masking area, sorted from smallest area to greatest. 
 *
 */
public class GrafixMask {
	public int[] sortedAreas(String[] rectangles) {
		int M = 400;
		int N = 600;
		boolean[][] visited = new boolean[M][N];
		
		for (int i=0; i<rectangles.length; i++) {
			String[] c = rectangles[i].split(" ");
			int top = Integer.parseInt(c[0]);
			int left = Integer.parseInt(c[1]);
			int bottom = Integer.parseInt(c[2]);
			int right = Integer.parseInt(c[3]);
			
			for (int x = top; x <= bottom; x++) {
				for (int y = left; y <= right; y++) {
					visited[x][y] = true;
				}
			}
		}
		
		ArrayList<Integer> result = new ArrayList<Integer>();
		
		for (int i=0; i<M; i++) {
			for (int j=0; j<N; j++) {
				if (!visited[i][j]) result.add(fill(i, j, visited, M, N));
			}
		}
		
		int[] areas = new int[result.size()];
		for (int i=0; i<result.size(); i++) areas[i] = result.get(i);
		Arrays.sort(areas);
		return areas;
	}
	
	private int fill(int x, int y, boolean[][] visited, int M, int N) {
		Stack<Point> stack = new Stack<Point>();
		stack.add(new Point(x, y));
		int count = 0;
		
		while (!stack.isEmpty()) {
			Point p = stack.pop();
			if (p.x < 0 || p.x >= M || p.y < 0 || p.y >=N || visited[p.x][p.y]) continue;
			
			count++;
			visited[p.x][p.y] = true;
			stack.push(new Point(p.x-1, p.y));
			stack.push(new Point(p.x+1, p.y));
			stack.push(new Point(p.x, p.y-1));
			stack.push(new Point(p.x, p.y+1));
		}
		
		return count;
	}
	
	private class Point {
		int x;
		int y;
		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
}
